package day0304

import (
	. "gocode/algorithm/utils"
	"math"
)

var res int

func maxPathSum(root *TreeNode) int {
	res = math.MinInt64
	help(root)
	return res
}

func help(root *TreeNode) int {
	if root == nil {
		return 0
	}
	l := max(0, help(root.Left))
	r := max(0, help(root.Right))
	res = max(res, l+r+root.Val)
	return root.Val + max(l, r)
}

func max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}
